﻿#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

/*
 88. 合并两个有序数组
给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n ,分别表示nums1和nums2中的元素数目。
请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
*/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m - 1;
    int end2 = n - 1;
    int end = m + n - 1;

    while (end1 >= 0 && end2 >= 0)
    {
        if (nums1[end1] > nums2[end2])
        {
            nums1[end--] = nums1[end1--];
        }
        else
        {
            nums1[end--] = nums2[end2--];
        }
    }
    while (end1 >= 0)
    {
        nums1[end--] = nums1[end1--];
    }

    while (end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}



/*
26. 删除有序数组中的重复项
给你一个升序排列的数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次,返回删除后数组的新长度。
元素的相对顺序应该保持一致 。
如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
*/

int removeDuplicates(int* nums, int numsSize) {
    int ps1 = 0;
    int ps2 = 1;
    int dest = 0;

    while (ps2 < numsSize)
    {
        nums[dest] = nums[ps1];
        dest++;

        if (nums[ps1] != nums[ps2])
        {
            ps1++;
            ps2++;
        }
        else
        {
            while (ps2 < numsSize && nums[ps1] == nums[ps2])
            {
                ps2++;
            }

            ps1 = ps2;
            ps2++;
        }
    }

    if (ps1 < numsSize)
    {
        nums[dest] = nums[ps1];
        dest++;
        //ps1++;
        //不需要考虑数组中超出新长度后面的元素。
    }

    return dest;
}


/*
189. 轮转数组
给你一个数组，将数组中的元素向右轮转k个位置，其中k是非负数。

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
*/

void reverse(int* a, int left, int right)
{
    while (left < right)
    {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
        left++;
        right--;
    }

}


void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}

int main()
{

	return 0;
}